package basic.study.algorithms.search;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
//dfs,bfs
public class BinarySearchTree {

    public void preOrder(Node node) {
        if(node == null) return ;
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
    public void inOrder(Node node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }
    public void postOrder(Node node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data);
    }
    //bfs
    private List<Node> floorLevelTree(Node root) {
        List<Node> result = new ArrayList<>();
        Node node = root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        while(!queue.isEmpty()) {
            node = queue.poll();
            result.add(node);
            if(node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return result;
    }
    //dfs
    public List<List<Integer>> res  = new ArrayList<>();
    public void dfs(Node node, int level) {
        if (node == null) return ;
        if (res.size() <= level) res.add(new ArrayList<>());
        res.get(level).add(node.data);
        dfs(node.left, level+1);
        dfs(node.right, level+1);
    }

    private Node tree;

    public Node find(int data) {
        Node p = tree;
        while (p != null) {
            if (p.data < data) p = p.right;
            else if(p.data > data) p = p.left;
            else return p;
        }
        return null;
    }
    public void insert(int data) {
        if (tree == null) {
            tree = new Node(data);
            return;
        }
        Node p = tree;
        while(p != null) {
            if (data < p.data) {
                if (p.left == null) {
                    p.left = new Node(data);
                    return ;
                } else {
                    p = p.left;
                }
            } else {
                if (p.right == null) {
                    p.right = new Node(data);
                    return ;
                } else {
                    p = p.right;
                }
            }
        }
    }

    public void delete(int data) {
        Node p = tree;
        Node pp = null;
        while(p!= null && p.data != data) {
            pp = p;
            if (p.data < data) p = p.right;
            else p = p.left;
        }
        if (p == null) return ;
        //找到了p，然后执行删除

        // 要删除的节点有两个子节点
        if (p.left != null && p.right != null) {
            Node minP = p.right;
            Node minPP = p;
            while(minP.left !=  null) {
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data;
            p = minP;
            pp = minPP; // 下面就变成了删除minP了
        }

        // 删除节点是叶子节点或者仅有一个子节点
        Node child;
        if (p.left != null) child = p.left;
        else if (p.right != null) child = p.right;
        else child = null;

        if (pp == null) tree = child;//删除的是根节点
        else if (pp.left == p) pp.left = child;
        else pp.right = child;
    }

    public Node findMin() {
        if (tree == null) return null;
        Node p = tree;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
    public Node findMax() {
        if (tree == null) return null;
        Node p = tree;
        while(p.right != null) {
            p = p.right;
        }
        return p;
    }

    public static class Node {
        public int data;
        public Node left;
        public Node right;

        public Node(int data) {
            this.data = data;
        }
    }
}
